﻿using System.Collections;
using System.Diagnostics;
using KinonekoSoftware.Extensions.Strings.Core;

namespace KinonekoSoftware.Extensions.Strings.SearchModels.TrieTree
{
    public class TrieTreeSearchPattern : TrieTreeSearchPatternBase, ISearchPattern
    {
        private static readonly MatchResult[] Empty = Array.Empty<MatchResult>();

        private int               _version;
        private IGlossaryProvider _glossary;

        static MatchResult GetMatchedResult(int offset, int length) => new MatchResult(offset, length, true);

        static MatchResult GetUnmatchedResult(int offset, int length) => new MatchResult(offset, length, false);

        public void Build(IGlossaryProvider glossary)
        {
            var root = ((ITrieTreeGlossaryProviderRoot)glossary).Root;

            //
            // 
            BuildFail(root);

            //
            //
            _glossary = glossary;

            //
            //
            _version = glossary.Version;
        }

        private static bool StartMatch(ref int i, char[] input, Node root, Node node, out MatchResult result)
        {
            var backend = i;
            var offset  = i++;
            var length  = 1;
            var str_len = input.Length;

            for (; i < str_len; i++)
            {
                //
                //
                var ch   = input[i];
                var next = node.Get(ch);

                //
                // 失配
                if (next is null)
                {
                    //
                    // 尝试寻找其他节点
                    while (node is null && !ReferenceEquals(node, root))
                    {
                        node = node.Fail;
                        next = node.Get(ch);
                    }

                    //
                    // 重新匹配成功
                    if (next is not null)
                    {
                        //
                        //
                        length++;
                        //
                        //
                        node = next;
                    }
                    else if (node.IsWordEnd)
                    {
                        //
                        // 匹配失败，但是是完整的节点。
                        i--;
                        
                        //
                        // 因为这一次指针向前，尝试匹配但是失败了，所以需要指针回退
                        result = GetMatchedResult(offset, length);
                        return true;
                    }
                    else
                    {
                        result = null;
                        return false;
                    }


                }
                else
                {
                    node = next;
                    length++;
                }
                //
                // if (node.IsWordEnd)
                // {
                //     if (i == input.Length - 1)
                //     {
                //         result = GetMatchedResult(offset, length);
                //
                //         return true;
                //     }
                //
                //     //
                //     //
                //     ch = input[i + 1];
                //     var temp = node.Get(ch);
                //
                //     if (temp is not null)
                //     {
                //         node = temp;
                //         length++;
                //         i++;
                //     }
                //     else
                //     {
                //         result = GetMatchedResult(offset, length);
                //
                //         return true;
                //     }
                //
                // }

            }

            if (backend != i && node.IsWordEnd)
            {
                result = GetMatchedResult(offset, length);
                return true;
            }
            
            //
            // TODO: 可能有错
            result = null;
            return false;
        }

        public IList<MatchResult> Match(string input)
        {
            if (string.IsNullOrEmpty(input))
            {
                return Empty;
            }

            if (_glossary is null)
            {
                return Empty;
            }

            var root    = ((ITrieTreeGlossaryProviderRoot)_glossary).Root;
            var offset  = 0;
            var results = new List<MatchResult>(16);
            var str_len = input.Length;
            var array   = input.ToCharArray();

            for (var i = 0; i < str_len; i++)
            {
                var ch   = array[i];
                var node = root.Get(ch);


                if (node is not null)
                {
                    var old = i;

                    if (StartMatch(ref i, array, root, node, out var newResult))
                    {
                        if (offset == 0 && newResult.Offset == offset)
                        {
                            results.Add(newResult);
                        }
                        else
                        {

                            results.Add(GetUnmatchedResult(offset, newResult.Offset - offset));
                            results.Add(newResult);

                        }
                        offset = old + newResult.Length;
                    }
                    else
                    {
                        i++;
                    }
                }

            }

            if (offset < str_len)
            {
                results.Add(GetUnmatchedResult(offset, str_len - offset));
            }

            return results;
        }

        public int Version => _version;

    }

    public abstract class TrieTreeSearchPatternBase
    {

        internal static void BuildFail(Node root)
        {
            var queue = new Queue<Node>();

            queue.Enqueue(root);

            while (queue.Count > 0)
            {
                //
                //
                var node = queue.Dequeue();

                foreach (var (key, child) in node.Children)
                {
                    if (node.Parent is null)
                    {
                        child.Fail = root;
                    }
                    else
                    {
                        GetFailure(root, child, node);
                    }

                    queue.Enqueue(child);
                }
            }
        }

        internal static void GetFailure(Node root, Node temp, Node parent)
        {
            var q = parent.Fail;
            var p = q.Get(temp.Value);

            if (p is null)
            {
                //
                //
                p = q.Fail;

                //
                // 一直查找parent的fail节点，除非遇到Root
                while (p is not null && ReferenceEquals(p.Fail, root))
                {
                    p = p.Get(temp.Value);

                    p = p?.Fail;
                }

                temp.Fail = p ?? root;
            }
            else
            {
                temp.Fail = p;
            }
        }
    }
}